Packet data networks are becoming increasingly important in today's economy. A good example of this is the Internet. The amount of traffic flowing over packet data networks, and especially IP networks, is increasing exponentially. The commercial value of the data communicated and the time spent communicating is increasing rapidly as well.
With the increased importance of packet networks has come increased scrutiny of the less desirable characteristics of such networks. The Internet provides global connectivity, but it is still unable to guarantee the throughput that will be experienced by a data connection. Response times vary widely. Real-time interactive communication requiring low delays is only marginally practical. There are an increasing number of applications whose success has been hampered or prevented by these problems.
To make it possible to successfully exploit the Internet and other packet data networks, it is necessary to control the QoS experienced by packets as they are being communicated across the packet data network. To deliver value-added services such as voice telephony, video conferencing, near real-time transaction processing and the like, the packet data network should control the bandwidth, delay, jitter, and reliability experienced by packets passing through the network. Since most packet data networks cannot provide the highest levels of QoS to all packets that they handle, a packet data network should provide individualized QoS treatment to a plurality of subsets of the packets transiting the network. Each subset is identified by classification rules that are used to categorize packets into classes according to the properties of the packets.
A specification of the QoS treatment to be provided in a packet data network can be considered to be a QoS policy. A QoS policy identifies a plurality of classes of packet traffic. Each class is defined by classification rules that specify the subset of packets that belong to the class. Each class can be associated with a level of QoS specifying, for example, the bandwidth, delay, jitter, and reliability treatment to be provided to packets belonging to the class. The policy may specify limits on the amount of traffic that will be admitted to the class.
The overall QoS policy for a packet data network may be embodied in a centralized policy server. Routers and other packet forwarding devices interact with the policy server to determine the QoS treatment that is to be provided to a subset of packets. FIG. 1 is a schematic diagram of a computer network with a central policy server. It shows computer 1 and computer 2 communicating via a data connection 30. Packets travel from computer 1 to computer 2 on a path which transits through routers 10, 12, 13, and 16. When one of these routers (typically the edge routers 10 and 16) needs to consult a QoS policy in order to determine the appropriate level of QoS to provide to the data connection, Common Open Policy Service (“COPS”) queries 40 and 41 are sent to policy server 20. Policy server 20 returns a COPS result after consulting its policy database 21 to retrieve information specifying the relevant policy. Where better scalability is desired, the overall QoS policy may be broken up into multiple QoS policies that are installed in local policy servers or even in each router.
FIG. 2 is a schematic diagram of a computer network with distributed policy servers. It shows computer 101 and computer 102 communicating via data connection 130. Packets from computer 101 transit through routers 110, 112, 113, and 116 in traveling to computer 102. Each router has a QoS policy stored in its own policy database. When any of these routers needs to consult a QoS policy in order to determine the appropriate level of QoS to provide to the data connection, it need only consult its local policy database.
Regardless of whether QoS policy is centralized or distributed, a variety of errors can occur in a QoS policy. Classification rules for a plurality of classes may overlap resulting in ambiguous treatment being specified for some subset of packets. If numerous classes are assigned a large bandwidth, the total bandwidth may exceed the available data link capacity in the data network. If many of the classes specify low delays, it may be impossible to satisfy these delay requirements if the packet traffic in these classes are competing for access to certain data links in the packet data network.
Before a QoS policy can be used, it should be verified in order to ensure that there are no errors in the policy. If a policy containing errors is used, packets may be lost, or the intended QoS treatment may not be provided to the packets.